class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* cur = pHead;
        struct ListNode* lguard, * gguard, * lstart, * gstart;
        lstart = lguard = (struct ListNode*)malloc(sizeof(struct ListNode));
        gstart = gguard = (struct ListNode*)malloc(sizeof(struct ListNode));
        while (cur)
        {
            if (cur->val < x)
            {
                lguard->next = cur;
                lguard = lguard->next;
            }
            else
            {
                gguard->next = cur;
                gguard = gguard->next;
            }
            cur = cur->next;
        }
        lguard->next = gstart->next;
        gguard->next = nullptr;
        return lstart->next;
    }
};



struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* tailA = headA, * tailB = headB;
    int lenA = 1;
    int lenB = 1;
    while (tailA != NULL)
    {
        tailA = tailA->next;
        lenA++;
    }
    while (tailB != NULL)
    {
        tailB = tailB->next;
        lenB++;
    }
    int num = abs(lenA - lenB);
    if (lenA > lenB)
    {
        while (num--)
        {
            headA = headA->next;
        }
    }
    else
    {
        while (num--)
        {
            headB = headB->next;
        }
    }
    tailA = headA;
    tailB = headB;
    while (tailA && tailB)
    {
        if (tailA == tailB)
        {
            return tailA;
        }
        tailA = tailA->next;
        tailB = tailB->next;
    }
    return NULL;
}



bool hasCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            return true;
        }
    }
    return false;
}